/*
https://leetcode.cn/problems/minimize-the-maximum-difference-of-pairs/
力扣2616
*/

class Solution {  
public:  
    int minimizeMax(vector<int>& nums, int p) {  
        sort(nums.begin(), nums.end());  
        int n = nums.size()-1; 
        function<bool(int)> check = [&](int mx) {
            int cnt = 0, i = 0;  
            while (i < n) {
                if (nums[i + 1] - nums[i] <= mx) { 
                    cnt++;  
                    i += 2; 
                } else {  
                    i++;
                }  
            }  
            return cnt >= p;  
        };  
        int l = 0, r = nums[n] - nums[0];
        while (l < r) {  
            int mid = (l+r)>> 1;  
            if (check(mid)) {  
                r = mid; 
            } else {  
                l = mid + 1; 
            }  
        }  
        return l;  
    }  
};